With the advent of small digital circuitry, there has been a fast-emerging industry in the area of digital systems employing memory products capable of maintaining charge storage even when power is no longer available to the system. Such products comprise of hand-held or palm-held digital personal computers (PCS), digital cameras, solid state floppy disks, and the like. These products typically employ non-volatile memories in order to retain the information being stored even when power is no longer supplied to the system. Non-volatile memory may be in the form of read-only-memory (ROM), programmable read-only-memory (PROM), electrically-erasable programmable read-only-memory (EEPROM) or flash memory.
The use of flash memories in small portable computers, is due in part to their capability to store a large amount of information in digital form while allowing fast retrieval of the stored information. Solid state memory such as in the form of flash memory is therefore an appealing alternative to the use of hard disk drives for mass storage in portable computers. Other reasons for the replacement of hard disks with flash memory are robustness and lower power consumption.
That is, hard disks are unable to withstand many of the kinds of physical shock that a portable computer will likely sustain. Additionally, the motor for rotating the disk consumes significant amounts of power thereby decreasing the battery life for portable computers. Flash memory chips however, for reasons of lacking mechanical components and various electrical characteristics associated therewith, generally consume less power than consumed by hard disk drives.
Flash memory is an array of transistor memory cells with each cell being programmable through hot electron, source injection, or tunneling, and erasable through Fowler-Nordheim tunneling. The programming and erasing of such a memory cell requires current to pass through the dielectric surrounding floating gate electrode causing such types of memory to have a finite number of erase-write cycles (a flash memory cell previously written can not be over-written before first being erased) prior to the deterioration of dielectric. Manufacturers of flash cell devices specify the limit for the number of erase-write cycles between 100,000 and 1,000,000.
One requirement for a semiconductor mass storage device to be successfully employed in lieu of a rotating media hard disk mass storage device is that such substitution must be transparent to the designer and the user of a system using such a device. In other words, the designer or user of a computer incorporating such a semiconductor mass storage device could simply remove the hard disk and replace it with a semiconductor mass storage device. Among other reasons, this allows all presently-available commercial software to operate on a system employing such a semiconductor mass storage device without the necessity of any modification. To replace the typical hard disk drive in PCs then, flash memory devices must readily read and write data being stored therein. Furthermore, as noted earlier, using flash memory devices requires erasing operations to be performed on flash cells in order to allow re-use thereof. However, due to the structure of flash cells, erase operations are not always conducted successfully. In order to assure appropriate erasure of cells, a system employing flash memory devices checks and verifies the outcome of an erase operation otherwise, the memory cell being programmed is likely to be effectively inoperative.
Upon detection of errors after the completion of an erase operation, it may be very important to determine which blocks, if any, within the flash memory devices, or which sectors within a block are in error. To date, prior art techniques either locate errors within a block in an inefficient manner thereby significantly contributing to reduction of system performance or are simply wasteful of what could be very expensive flash memory. It is therefore pertinent to devise a method and apparatus for locating errors, within a block (sector or byte, as the case may be) that has been detected as having errors, in an efficient and inexpensive manner. At this time, a general understanding of the structure and format of a hard disk drive is provided.
As is well known to designers in the PC industry, information that is stored in typical hard disk drives of PCs is organized in the form of sectors. Each sector is apportioned to include user data and extension information (sometimes referred to as overhead or header field). FIG. 1 shows an example of a sector 10, illustrated to include 512 bytes of data 12(each byte being 8 bits) and 12 bytes of overhead information or extension 14. Extension field 14 is further shown to include an error detection/correction portion 16 and a sector book-keeping portion, which are each 6 bytes, for storing the sector's overhead information. The extension field 14 may include information regarding defects in a sector, error correction codes (ECC) in association with the sector data and other information that the designer of a disk drive system may need for employing a particular sector format as may be specified by the manufacturer of a disk drive. The discussion concerning sector organization is briefly interrupted to provide the reader with an overview on the incorporation of the sector format within a PC system.
FIG. 2 illustrates a portable PC system 17 (such as a notebook, palm-held or hand-held computer) having a PCMCIA card slot 18 for coupling a PC ATA card 20, having electronics circuitry residing thereon, into the host computer 22 for communication of digital information therebetween when the PC ATA card 20 is inserted in the PCMCIA slot 18. The PC ATA card 20 may be a substitute for the PC system's hard disk (or enhancement thereof) such that data that is normally stored in a hard disk drive is instead stored in and retrieved from the PC ATA card. This clearly contributes to the compactness of the PC system 17 since PC ATA cards are generally much smaller in-size than hard disk drives. While not shown in FIG. 2, non-volatile (more specifically, flash) memory chips for storage of data and a microprocessor or microcontroller along with appropriate ROM and/or RAM memory devices are generally included in the PC card 20. The electronic circuitry residing on PC ATA card 20 may be alternatively an embedded rather than a removable structure permanently included within the computer 22. As is appreciated by those of ordinary skill in the art, the PCMCIA slot 18 may alternatively use interfaces other than a PCMCIA interface. Such other interfaces include PC card, compact flash, ATA, PCI, parallel, serially, etc.
Turning the discussion back to the need for a method of determining which block section or byte has caused an erase operation to fail, the reader is reminded that in order to perform valid operations on the data being stored in flash memory chips, it is necessary to locate the block, sector, or byte that has caused the erase operation to fail and marking it defective so as to minimize the risk of using a defective or incompletely-erased area of memory for data storage. FIG. 3 provides a flow chart of a prior art method for verification of erase operations. Normally, the microprocessor, residing in PC card 20 (in FIG. 2, executes software program code designed to perform the steps outlined in FIG. 3 from the ROM or RAM memories residing on the PC card.
Typically, erasing is performed on a group of sectors, referred to as a block, and therefore checking for successful erases is similarly performed on a block. Initially, in steps 22, counter CNTR A is set equal to the number of sectors within a block that are to be checked. Using the 256-sector block size example, CNR A is set equal to the value of 256. A second counter, in step 24, namely counter CNTR B, is set equal to the number of bytes within a sector. Using the 512-byte sector size example of FIG. 1, CNTR B is set equal to the value 512, which represents 512 bytes of sector data. In step 26, a loop begins with the first byte of the first sector within the block being read. Next, the byte that is read is compared to the value `FF` (hexadecimal notation) as shown by step 28. The reason for this comparison is due to the erasure characteristics of flash memory cells, i.e. successful erasure of a cell should effect a digital value of `1` upon reading of the cell. Thus, where a cell stores one bit of data, reading one byte of data should result in the value `FF` if all of the cells within the byte are appropriately erased.
In FIG. 3, if the result of the comparison yields a match between the byte read and the value `FF`, the counter CNTR B is decremented by one. In this example, CNTR B would be 511 after it is decremented (step 30) and if the value in CNTR B is not zero (or the last byte of the first sector is not yet checked) steps 26-32 are repeated a total of 512 times.
Referring back to step 28, if any of the bytes are not read as having the value `FF`, the entire sector is marked defective (step 34) and the loop is exited. Upon either completion of the loop or detection of a defective sector, counter CNTR A is decremented by one in step 36 in preparation for verification of the next sector. In step 38, counter CNTR A is compared to zero for a determination of whether all of the sectors have been verified and if not counter CNTR B is again reset to the value representing the number of bytes in a sector; in our example this value is 512. Steps 26-32 are again repeated 512 times until all of the sectors have been checked for defects.
One problem arising in prior art systems using techniques similar to that shown in FIG. 3 is that a long time is required for checking a block of sectors for appropriate erasure thereof. This is due to two factors, one is that a microprocessor is executing software code check for errors which is a very slow process. For example, a microprocessor used in solid state storage cards (i.e. PC card 20 in FIG. 2) typically executes an instruction in 4 instruction cycles, with each instruction cycle requiring 50 nanoseconds to execute. Each of the steps outlined in FIG. 3 is executed using at least one microprocessor program instruction, which is very time consuming thereby resulting in a reduction of system performance.
As is clear to those skilled in the art, the larger the block size, the longer time needed for checking for proper erasure of sectors. Therefore, the system of prior art, as shown to perform in accordance with FIG. 3 significantly decreases system performance particularly when larger block sizes are employed. Furthermore, flash memory characteristically has tendency to fail more often as it is further used. In other words, an old flash memory device that has been in frequent operation, is likely to return errors when being read, written to or erased. In this respect, the method of prior art systems requiring lengthy check for erase times, are even less effective when used with aged flash devices. This gain leads to significant system degradation as the prior art system in continuously in operation.
One of the factors leading to degradation of system performance using prior art techniques is the number of times instructions are repeated in order to check a block of sectors. In fact, the number of times instructions are repeated is directly correlated with the size of the block being checked for proper erasure, i.e. the larger the block, the longer the time required for verifying whether the block was properly erased. To use the above example, steps 26-32 in FIG. 3 are executed 512 times per sector if no defective byte is detected. Since each sector contains 512 bytes, steps 26-32 as shown in FIG. 3 are executed up to a total of 512.times.256 times and steps 36 and 38 as shown in FIG. 3, are executed 256 times, with each instruction requiring at least 4 program instruction cycles to execute. Therefore, at least 21.5 milliseconds are required to verify a block having 256 sectors using the prior art technique of FIG. 3.
In other prior art methods, when a block is found to be defective after the performance of an erase operation, it is likely to be discarded and not used further. This technique is especially prevalent in systems using small block sizes such as for example, 4K byte block size. Systems doing so, generally balance the waste in discarding blocks against the benefit in saving time by eliminating identification of particular sector or byte within the block that are causing errors and find such waste to be tolerable generally for small block sizes. However, efficient ways of identifying errors within a sector or byte inside of a block are likely to prevent the need for such waste of memory in prior art system. Additionally, with larger block sizes, it becomes important to reuse a block that has been found defective if the area in which error(s) exist can be identified and discarded.
As can be appreciated, a system is needed to efficiently locate a sector within a block that has failed the erase operation without degrading system performance. Such a system has particular application in PC systems employing flash memory devices to replace and/or enhance hard disk drives as mass storage wherein erase operations are frequently required to allow write operations to the same location performed on non-volatile solid state memory devices employed in digital systems without degrading system performance.